home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / BARNET / COMPILER / SATHER / !Sather / Library / Graphs / sa / abs_graph < prev    next >
Text File  |  1996-07-13  |  2KB  |  64 lines
  1. ---------------------------> Sather 1.1 source file <--------------------------
  2. -- Author: Benedict A. Gomes <gomes@samosa.ICSI.Berkeley.EDU>
  3. -- Copyright (C) 1995, International Computer Science Institute
  4. -- COPYRIGHT NOTICE: This code is provided WITHOUT ANY WARRANTY
  5. -- and is subject to the terms of the SATHER LIBRARY GENERAL PUBLIC
  6. -- LICENSE contained in the file: Sather/Doc/License of the
  7. -- Sather distribution. The license is also available from ICSI,
  8. -- 1947 Center St., Suite 600, Berkeley CA 94704, USA.
  9. -------------------------------------------------------------------
  10. abstract class $GRAPH{NTP<$HASH,ETP< $EDGE{NTP}} < $ELT{NTP}, $STR is
  11.    -- A generic graph, consisting of a bunch of nodes and edges.
  12.    -- There is no committment as to the meaning of the edges
  13.    -- Every node has some edges which associate it with a set of 
  14.    -- neighbors
  15.    -- This generic graph does not have the modification operations
  16.    -- Design note:
  17.    --   The reason for not having the modification operations is that
  18.    --   it is hard to work on a general graph without knowing whether it
  19.    --   has directed or undirected edges
  20.    -- Acknowledgement:
  21.    --   Discussions with the Karla folk, particularly Wolf, helped
  22.    --   elucidate some of the confusion between directed and undirected 
  23.    --   graphs
  24.    
  25.    is_empty: BOOL;
  26.    -- Return true if there are no nodes in the graph
  27.    
  28.    copy: $GRAPH{NTP,ETP};
  29.    -- Return a copy of the graph
  30.    
  31.    n_nodes: INT;
  32.    -- Return the number of nodes in the graph
  33.    
  34.    n_edges: INT;
  35.    -- Return the number of edges in the graph
  36.    
  37.    has_node(n: NTP): BOOL;
  38.    -- Return  true if this graph has the node "n"
  39.    
  40.    has_edge(e: ETP): BOOL;
  41.    -- Return true if this graph has the edge "e"
  42.    
  43.    n_adjacent(n: NTP): INT;
  44.    -- Return the number of nodes that are adjacent to "n".
  45.    -- See the note at "adjacent!"
  46.    
  47.    node!: NTP;
  48.    -- Yield all the nodes in the graph
  49.    
  50.    edge!: ETP;
  51.    -- Yield all the edges in the graph
  52.    
  53.    adjacent!(once n: NTP): NTP;
  54.    -- This corresponds more closely to the notion of neighbors in an
  55.    -- undirected graph. In the case of a directed graph, the neighbors
  56.    -- will be the set of outgoing nodes.
  57.    -- In other words, by going through all nodes and their adjacent
  58.    -- nodes we can construct all the edges in the graph without
  59.    -- duplication.
  60.    
  61. end; -- class $GRAPH{NTP,ETP}
  62. -------------------------------------------------------------------
  63.  
  64.